package com.study.lintcode.my.code_10;

import java.util.LinkedList;
import java.util.Queue;

/**********************************************************************
 * &lt;p&gt;文件名：Example_1.java &lt;/p&gt;
 * &lt;p&gt;文件描述：(https://www.lintcode.com/problem/a-b-problem/)
 * @project_name：LintCode
 * @author zengshunyao
 * @create 2019/1/5 21:56
 * @history
 * @department：政务事业部
 * Copyright ChengDu Funi Cloud Code Technology Development CO.,LTD 2014
 *                    All Rights Reserved.
 */
public class Example_7 {
    public static Queue<TreeNode> queue = new LinkedList<TreeNode>();//用于保存将树结构序列化成字符串时使用来保存
    public static Queue<TreeNode> dataqueue = new LinkedList<TreeNode>();//用于将字符串结构反序列化成树时使用来保存节点
    public String string = "";

    /**
     * This method will be invoked first, you should design your own algorithm
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    public String serialize(TreeNode root) {
        // write your code here
        //3,9,20,#,#,15,7
        if (root == null) {
            return "#";
        } else {
            queue.add(root);//根节点不为空，加入队列
            while (!queue.isEmpty()) {//直到队列为空，才跳出循环
                TreeNode treeNode = queue.poll();//每次取出队列的第一的节点
                if (treeNode == null)//如果为空，那么直接输出“#”，不再把该点的左右子节点加入队列
                    string = string + "#" + ",";
                else {//该节点不为空，则把该点的值加上在字符串后面
                    string = string + treeNode.val + ",";
                    queue.add(treeNode.left);//该节点不为空，那么它的左右子节点都要加进去，可能为空，可能不为空，加进去不判断
                    queue.add(treeNode.right);//从队列中取出来才判断是不是为空，为空则没有下一层了
                }
            }
        }

        string = string.lastIndexOf(",") == string.length() - 1 ?
                string.substring(0, string.length() - 1) : string;//将后面的“，”去掉
        return string.equals("#") ? "" : string;

    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in
     * "serialize" method.
     */
    public TreeNode deserialize(String data) {
        // write your code here
        if (data.equals("")) {
            return null;
        }
        if (data.equals("#")) {
            return null;
        }
        String nodes[] = data.split(",");
        TreeNode root, head, left, right;
        root = head = left = right = null;
        if (nodes[0].equals("#")) {
            return null;
        }
        root = head = new TreeNode(Integer.valueOf(nodes[0]));
        for (int i = 1; i < nodes.length; i += 2) {
            left = nodes[i].equals("#") ? null : new TreeNode(Integer.valueOf(nodes[i]));
            right = nodes[i + 1].equals("#") ? null : new TreeNode(Integer.valueOf(nodes[i + 1]));
            head.left = left;
            head.right = right;
            if (left != null) {
                dataqueue.add(left);
            }
            if (right != null) {
                dataqueue.add(right);
            }
            if (!dataqueue.isEmpty())
                head = dataqueue.poll();
        }
        return root;
    }

    public static class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }

    }


    public static void main(String[] args) {

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(new Example_7().serialize(root));
        System.out.println(new Example_7().serialize(
                new Example_7().deserialize("3,9,20,#,#,15,7,#,#,#,#")));
    }
}
